《剑指offer》 19.正则表达式匹配

剑指offer
留言

note:两个字符串匹配的问题，经典的解法就是使用二维dp数组进行动态规划求解，因为显然字符串匹配就是一个可以分解为小问题、依赖小问题来解决大问题的问题。

题目描述

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但与”aa.a”和”ab*a”均不匹配。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 ‘.’ 和’*‘，无连续的 ‘*’。

方法一： 二维动态规划

思路

两个字符串的匹配问题，可以转换为二维动态规划问题。

两个字符串的匹配是非常复杂的，但是单个的字符匹配是简单的，动态规划解决字符串匹配的问题的关键就是考虑到，我们可以转化的小问题，是匹配两个字符串的各个子串。

我们考虑使用dp[m][n]数组来表示动态规划存储的匹配方案，$dp[i][j]$表示$s$前$i$个字符和$p$前$j$个字符是否可以匹配。

接下来我们分情况进行讨论

  • $p$的第$j$ 个字符是字母。由于$s$中都是字母，那么很显然如果当前两个字符相同，前面的子串可以匹配，那自然新的子串也可以进行匹配。这种情况的状态转移方程非常简单：

  • $p$的第$j$个字符是’.’。由于’.’可以匹配任何一个字符，那它的转移方程更为简单：

  • $p$的第$j$个字符是’*‘。这种情况就比较复杂了，因为’*‘的匹配规则是“它前面的字符可以出现任意次（含0次）”也就是说$p$第$j$个位置出现*号时我们就要考虑第$j-1$个字符的情况。此时我们可以列出来该字符出现若干次时的状态转移

    • 出现0次：$dp[i][j] = dp[i][j-2]$。含义就是既然我第$j-1$个字符没有出现，那么我$s$字符串中的第$i$个字符就不应该和我第$j-1$个字符进行匹配，而应该和再往前一个字符匹配，也就是第$j-2$个字符。
    • 出现1次并且和$s$中的第$i$个元素成功匹配：$dp[i][j]=dp[i-1][j-2]$，向前匹配
    • 出现2次并且和$s$中的第$i$个、第$i-1$个元素成功匹配：$dp[i][j] = dp[i-2][j-2]$,继续向前匹配
    • ·········

    根据这个过程，我们可以得出一个状态转移方程

    理解为当$p$中第$j-1$个元素不等于$s$中第$i$个元素时（匹配失败），就将第$j-1$个元素视作出现0次处理。将$s$中的第$i$个元素和$p$中的第$j-2$个元素对比，如果匹配成功，则考虑多种情况，既有可能虽然匹配成功，但是该元素不一定要出现（0次出现），也有可能该次出现有效，往前溯源看前面是否相同。

最后的话我们总结三种状态转移方程，得到一个整体的转移方程如下：

match(x,y)是我们做的匹配过程，为了提高程序的复用性，我们可以写成c++11标准中的lambda表达式，lambda表达式用于定义并创建匿名的函数对象，以简化编程。使用格式如下：

1
2
3
[函数对象参数] (操作符重载函数参数) mutable  ->返回类型  { 
	函数体
}；

具体介绍和使用我后面会写一篇额外的博客，这儿就不赘述了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));

        auto match = [&](int x,int y){
            if(x==0)
                return false;
            if(p[y-1]=='.')
                return true;
            else
                return s[x-1]==p[y-1];
        };

        dp[0][0] = true;    // 长度为0的两个子串匹配必然匹配得上
        for(int i=0;i<=m;i++){      //s字符串从零匹配
            for(int j=1;j<=n;j++){  //p字符串考虑从1开始，因为*号不可能出现在0位置
                if(p[j-1]=='*'){
                    dp[i][j] = dp[i][j-2];  // 加入j-2的位置的元素出现为0次。
                    if(match(i,j-1)){  
                        dp[i][j] = dp[i][j] || dp[i-1][j]; 
                    }
                }else{
                    if(match(i,j)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];

    }
};

复杂度分析

  • 时间复杂度$O(mn)$。m、n分别为字符串长度
  • 空间复杂度$O(mn)$。dp数组的大小为m*n